package com.zhugang.week08;

import java.util.ArrayList;
import java.util.List;

/**
 * @program algorithms
 * @description: eightQueue
 * @author: chanzhugang
 * @create: 2022/08/03 17:51
 */
public class EightQueen {

    /**
     * 八皇后问题
     *
     * @return
     */
    List<char[][]> result = new ArrayList<>();

    public List<char[][]> eightQueen() {
        char[][] board = new char[8][8];
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                // 构造棋盘
                board[i][j] = '*';
            }
        }
        backtrack(0, board);
        return result;
    }

    /**
     * @param row   阶段
     * @param board 路径
     *              可选列表，通过board推导出来，没有显式记录
     */
    private void backtrack(int row, char[][] board) {
        if (row == 8) {
            // 结束条件，得到可行解
            char[][] snapshot = new char[8][8];
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {
                    snapshot[i][j] = board[i][j];
                }
            }
            result.add(snapshot);
            return;
        }

        for (int col = 0; col < 8; col++) {
            // 可选列表
            if (isOk(board, row, col)) {
                // 做选择，第row行的棋子放在col列
                board[row][col] = 'Q';
                // 考察下一行
                backtrack(row + 1, board);
                // 恢复选择
                board[row][col] = '*';
            }
        }
    }

    /**
     * 判断row行col列放置是否合适
     *
     * @param board
     * @param row
     * @param col
     * @return
     */
    private boolean isOk(char[][] board, int row, int col) {
        int n = 8;
        // 检查列是否有冲突
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }

        // 检查右上对角线是否冲突
        int i = row - 1;
        int j = col + 1;
        while (i >= 0 && j < n) {
            if (board[i][j] == 'Q') {
                return false;
            }
            i--;
            j++;
        }

        // 检查左上对角线是否有冲突
        i = row - 1;
        j = col - 1;
        while (i >= 0 && j >= 0) {
            if (board[i][j] == 'Q') {
                return false;
            }
            i--;
            j--;
        }

        return true;
    }
}